package com.swjd.tree;

/**
 * 线索化二叉树
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        //测试
        HeroNode2 tom = new HeroNode2(1, "汤姆");
        HeroNode2 jack = new HeroNode2(3, "jack");
        HeroNode2 smith = new HeroNode2(6, "smith");
        HeroNode2 mary = new HeroNode2(8, "mary");
        HeroNode2 king = new HeroNode2(10, "king");
        HeroNode2 dim = new HeroNode2(14, "dim");

        tom.setLeft(jack);
        tom.setRight(smith);
        jack.setLeft(mary);
        jack.setRight(king);
        smith.setLeft(dim);

        BinaryTree2 binaryTree2 = new BinaryTree2();
        binaryTree2.setRoot2(mary);
        binaryTree2.threadedNodes(tom);

        System.out.println(king.getLeft());

        System.out.println("使用线索化的方式中序遍历线索化二叉树");
        binaryTree2.threadedList();
    }
}

/**
 * 二叉树
 */
class BinaryTree2 {
    private HeroNode2 root;
    //为了实现线索化，需要创建一个指向前驱节点的指针
    private HeroNode2 pre = null;

    public void setRoot2(HeroNode2 root) {
        this.root = root;
    }

    /**
     * 中遍历线索化二叉树
     */
    public void threadedList() {
        //临时存储当前遍历节点
        HeroNode2 node2 = root;
        while (node2 != null) {
            //循环找到leftType==1的节点,第一个找到的就是第一个节点
            if (node2.getLeftType() == 0) {
                node2 = node2.getLeft();
            }
            //打印这个节点
            System.out.println(node2);
            //如果当前节点的右指针指向的是后继节点，就一直输出
            while (node2.getRightType() == 1) {
                //获取后继节点
                node2 = node2.getRight();
                System.out.println(node2);
            }
            //替换遍历的节点 继续循环，知道node2等于null，就代表右边已经没有数据了，跳出循环
            node2 = node2.getRight();
        }
    }

    /**
     * 中序线索化
     *
     * @param node2 需要线索化的节点
     */
    public void threadedNodes(HeroNode2 node2) {
        if (node2 == null) {
            return;
        }
        //线索化左子树
        threadedNodes(node2.getLeft());
        //线索化当前节点
        //先处理前驱节点
        if (node2.getLeft() == null) {
            //当前节点左指针是空，那么就将左指针指向前驱节点
            node2.setLeft(pre);
            //改变左指针状态，代表指向的是前驱节点
            node2.setLeftType(1);
        }

        //处理后继节点
        if (pre != null && pre.getRight() == null) {
            pre.setRight(node2);
            pre.setRightType(1);
        }
        pre = node2;
        //线索化右子树
        threadedNodes(node2.getRight());
    }

    /**
     * 前序遍历
     */
    public void preorder() {
        if (this.root != null) {
            this.root.preorder();
        } else {
            System.out.println("二叉树空！无法遍历");
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树空！无法遍历");
        }
    }

    /**
     * 后序遍历
     */
    public void afterOrder() {
        if (this.root != null) {
            this.root.afterOrder();
        } else {
            System.out.println("二叉树空！无法遍历");
        }
    }

    /**
     * 前序遍历查找
     *
     * @param no 要查找的英雄编号
     * @return 查找到的节点
     */
    public HeroNode2 preorderFind(int no) {
        if (this.root != null) {
            return root.preorderFind(no);
        } else {
            return null;
        }
    }

    /**
     * 中序遍历查找
     *
     * @param no 需要查找的编号
     * @return 查找到的节点
     */
    public HeroNode2 infixOrderFind(int no) {
        if (this.root != null) {
            return root.infixOrderFind(no);
        } else {
            return null;
        }
    }

    /**
     * 后序遍历查找
     *
     * @param no 需要查找的编号
     * @return 查找到的节点
     */
    public HeroNode2 afterOrderFind(int no) {
        if (this.root != null) {
            return root.afterOrderFind(no);
        } else {
            return null;
        }
    }

    /**
     * 删除节点
     *
     * @param no 需要删除节点的编号
     */
    public void delNode(int no) {
        if (root != null) {
            if (root.getNo() == no) {
                root = null;
            } else {
                root.delNode(no);
            }
        } else {
            System.out.println("空树，无法删除！");
        }
    }
}

/**
 * 英雄树节点
 */
class HeroNode2 {
    private int no;//编号
    private String name;//名字
    private HeroNode2 left;//左子节点
    private HeroNode2 right;//右子节点
    private int leftType;//为0表示指向的是左子树，为1表示指向前驱节点
    private int rightType;//为0表示指向右子树，为1表示后继节点


    public HeroNode2(int no, String name) {
        this.no = no;
        this.name = name;
    }

    @Override
    public String toString() {
        return "HeroNode2{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public int getLeftType() {
        return leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode2 getLeft() {
        return left;
    }

    public void setLeft(HeroNode2 left) {
        this.left = left;
    }

    public HeroNode2 getRight() {
        return right;
    }

    public void setRight(HeroNode2 right) {
        this.right = right;
    }

    /**
     * 前序遍历
     */
    public void preorder() {
        System.out.println(this);//先输出父节点
        //递归左子树
        if (this.left != null) {
            this.left.preorder();
        }
        //递归向右子树
        if (this.right != null) {
            this.right.preorder();
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);//打印父节点
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    /**
     * 后序遍历
     */
    public void afterOrder() {
        if (this.left != null) {
            this.left.afterOrder();
        }
        if (this.right != null) {
            this.right.afterOrder();
        }
        System.out.println(this);
    }

    /**
     * 前序遍历查找
     *
     * @param no 要查找的英雄编号
     * @return 查找到的节点
     */
    public HeroNode2 preorderFind(int no) {
        HeroNode2 resNode = null;
        if (this.no == no) {//如果编号相同 就返回
            return this;
        }
        if (this.left != null) {
            resNode = this.left.preorderFind(no);//继续向左遍历查找 如果查找到了就会给resNode值
        }
        if (resNode != null) {
            //不为空就代表找到了
            return resNode;
        }
        if (this.right != null) {
            resNode = this.right.preorderFind(no);//继续向右遍历查找 如果查找到了就会给resNode值
        }
        return resNode;//由于上面的左右都以及全部遍历完成了，所以这里无论是否找到都需要返回结果了
    }

    /**
     * 中序遍历查找
     *
     * @param no 需要查找的编号
     * @return 查找到的节点
     */
    public HeroNode2 infixOrderFind(int no) {
        HeroNode2 resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderFind(no);
        }
        if (resNode != null) {
            return resNode;
        }
        if (this.no == no) {
            return this;
        }
        if (this.right != null) {
            resNode = this.right.infixOrderFind(no);
        }
        return resNode;
    }

    /**
     * 后序遍历查找
     *
     * @param no 需要查找的编号
     * @return 查找到的节点
     */
    public HeroNode2 afterOrderFind(int no) {
        HeroNode2 resNode = null;
        if (this.left != null) { //如果左节点不为空，继续递归
            resNode = this.left.afterOrderFind(no);
        }
        if (resNode != null) {//如果resNode有值了，就代表上面的递归找打了
            return resNode;
        }
        if (this.right != null) {//如果右节点不为空，就继续递归
            resNode = this.right.afterOrderFind(no);
        }
        if (resNode != null) {//如果resNode有值了，就说明上面的递归找到了
            return resNode;
        }
        if (this.no == no) {//如果左边右边都没找到，就判断当前的
            return this;
        }
        return null;//左节点没找到，右节点没找到，当前节点没找到,就可以返回空了
    }

    /**
     * 删除节点
     *
     * @param no 需要删除的节点编号
     */
    public void delNode(int no) {
        //首先判断左子节点不为空，如果为空直接判断no的话容易报空指针异常
        if (this.left != null && this.left.no == no) {
            //如果要删除的子节点右边不为空
            if (this.left.right != null) {
                //就将节点的左边挂到节点的右边的左边上，再将右节点替换掉删除的节点
                this.left.right.left = this.left.left;
                this.left = this.left.right;
                return;
            }
            //如果左节点不为空，右节点为空，就直接将左节点替换该节点
            if (this.left.left != null) {
                this.left = this.left.left;
                return;
            }
            //左右都为空就代表该节点为叶子节点，就直接置为空
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no) {
            //如果要删除的子节点右边不为空
            if (this.right.right != null) {
                //就将节点的左边挂到节点的右边的左边上，再将右节点替换掉删除的节点
                this.right.right.left = this.right.left;
                this.right = this.right.right;
                return;
            }
            //如果左节点不为空，右节点为空，就直接将左节点替换该节点
            if (this.right.left != null) {
                this.right = this.right.left;
                return;
            }
            this.right = null;
            return;
        }
        if (this.left != null) {
            this.left.delNode(no);
        }
        if (this.right != null) {
            this.right.delNode(no);
        }
    }

}
